% Origin: 20091014, SPbSU Group A1 Fourth Training - Greedy Algorithms
% Author: Ivan Kazmenko (classic)
% Text Author: Ivan Kazmenko
% Tests Author: Ivan Kazmenko

\begin{problem}{Декодирование}
{decoding.in}{decoding.out}
{2 секунды}{256 Мебибайт}

В этой задаче по набору беспрефиксных кодов букв и строке, закодированной
с помощью этих кодов так, как это описано в задаче \textbf{``Кодирование''},
нужно восстановить исходную строку.

\InputFile

В первой строке входного файла заданы два целых числа $k$ и $l$ через
пробел "--- количество различных букв, встречающихся в строке,
и размер получившейся закодированной строки, соответственно.
В следующих $k$ строках записаны коды букв в формате
``\t{<letter>: <code>}''. Ни один код не является префиксом другого.
Буквы могут быть перечислены в любом порядке. В качестве букв могут
встречаться лишь строчные буквы латинского алфавита; каждая из этих букв
встречается в строке хотя бы один раз.
Наконец, в последней строке записана закодированная строка.

Исходная строка и коды всех букв непусты.
Заданный код таков, что закодированная строка имеет
минимальный возможный размер.

\OutputFile

В первой строке выходного файла выведите строку $s$.
Она должна состоять из строчных букв латинского алфавита.
Гарантируется, что длина правильного ответа не превосходит
$100\,000$ символов.

\Examples

\begin{example}
\exmp{
1 1
a: 0
0
}{
a
}%
\exmp{
4 14
a: 0
b: 10
c: 110
d: 111
01001100100111
}{
abacabad
}%
\end{example}
\end{problem}
